The present invention relates to the efficient and reliable transmission of packet or cell-based information, such as frame relay, SS#7, ISDN, Internet or asynchronous transfer mode (ATM) based information, via wireless links. More specifically, the present invention relates to a method and apparatus for minimization of cell or packet delay variance in satellite or wireless terrestrial networks that convey the traffic via Time Division Multiple Access (TDMA) or Time Division Multiplexing (TDM) techniques. While the present invention is applicable all of the foregoing types of transmission formats, the ATM format will be the exemplary focus of one preferred embodiment for purposes of providing an enabling disclosure, written description and best mode for the present invention.
There are a variety of methods for transmitting information via a broadband Integrated Services Digital Network (B-ISDN), using a variety of protocols related to Asynchronous Transport Mode (ATM), frame relay mode, Internet, ISDN and SS#7 modes of transmission. The ATM mode, as the exemplary preferred embodiment, was originally investigated by a group called the International Telephone and Telegraph Consultative Committee (CCITT). The group, currently called the International Telecommunication Union-Telecommunications Standards Sector (ITU-TSS), investigated a new form of ISDN that would have the flexibility to accommodate a large number of channels and the ability to transfer large amounts of data at a very fast rate. At the end of the study, the Committee decided to adopt ATM as the target transfer mode for the B-ISDN. The ITU-TSS is currently defining the wide area network (WAN) standards for ATM.
ATM is a transfer mode that sends 53 octet-sized packets of information across a network from one communication device to another. The 53 octets are assembled as a xe2x80x9ccellxe2x80x9d, which comprises 48 octets of data information, referred to as the xe2x80x9cpayloadxe2x80x9d, and 5 octets of xe2x80x9cheaderxe2x80x9d information (including the routing information). The header and data information must be organized into cells so that when the cells are filled, they can be sent when an open slot of 53 octets becomes available.
There are two forms of headers that are specified in the CCITT Recommendation I.361. Each form is 5 octets long. There also are two different ATM network connections, each one having a different type of header. One connection form is the user-network interface (UNI), which is used between the user installation and the first ATM exchange and also within the user""s own network. The other form of connection is the network-node interface (NNI) which is used between the ATM exchanges in the trunk network. The header format for the UNI consists of the following fields:
Generic flow control (GFC) field of 4 bits. It can provide flow control information towards the network from an ATM endpoint.
Routing field of 24 bits. Eight of the bits are VPI (virtual path identifiers) and 16 bits are VCI (virtual channel identifier). Empty cells with both the VCI and VPI set to zero indicates that the cell is unassigned.
Payload type (PT) field of 3 bits. This field is used to provide information on whether the cell payload contains user information or network information. This field is used by the network to intercept any important network information.
Cell loss priority (CLP) field containing 1 bit. This field may be set by the user or service provider to indicate lower priority cells. If the bit is set to 1 the cell is at a risk of being discarded by the network during busy times.
Header error control (HEC) field of 8 bits. This field is processed by the physical layer to detect errors in the header. The code used for this field is capable of either single-bit error-correction or multiple-bit error-detection.
As seen in FIGS. 1A and 1B, the header format for the NNI is the same as the header information of the UNI except that there is no GFC, and the VPI of the routing field is 12 bits instead of 8 bits.
Error detection occurs only within the header message. No error detection of the data occurs within the information portion of the cell. The receiving endpoint determines whether the data can be corrected or whether it must be discarded. When a link or node becomes busy, an ATM network must discard cells until the problem is resolved. The first cells to be discarded are the cells that have a CLP bit in the header set to a xe2x80x9c1xe2x80x9d. Since connection endpoints are not notified when a cell is discarded, higher layers of protocols are needed to detect and recover from errors.
A cell is sent along a channel called a Virtual Channel (VC) or Virtual Channel Connection (VCC). A VCC consists of a series of links that establish a unidirectional connection through the network that allows the flow of information from one endpoint to another endpoint. Cells on a VCC always follow the same path through the network. Therefore, each cell arrives at its destination in the same order in which it was transmitted. VCCs can be unidirectional or may occur in pairs, thus making the connection bi-directional. VCCs can be within a path called a Virtual Path (VP) or Virtual Path Connection (VPC), meaning a group of virtual channels that are associated together, so as to be sent as a large trunk for a part of network. The VCCs are multiplexed and demultiplexed at appropriate network nodes in the network. Each VCC and VPC have specially assigned numbers called Virtual Channel Identifiers (VCI) and Virtual Path Identifiers (VPI), respectively. These numbers help the system determine the direction in which the cells belonging to the connection should be sent and which applications should be associated with the connection.
Although ATM-based transmission, switching, and network technology has been employed in broadband integrated services digital networks (B-ISDN) which rely on fiber optics, there are numerous difficulties associated with implementing ATM based technology in a wireless communication network. These difficulties include the fact that ATM-based networks and switches rely on a number of high speed interfaces. These high-speed standard interfaces include OC-3 (155 Mbit/s), OC-12 (622 Mbit/s) and DS3 (45 Mbit/s). However, a few ATM based networks and switches support lower speed interfaces, such as T1 (1.544 Mbit/s) and the programmable rate RS-449 interface.
As a consequence, there are only a few interfaces which can support the comparatively low transmission rates (less than 1 Mbit/s to a 8 Mbit/s) used in wireless communication. Although commercial satellite and wireless modems support these low transmission rates using an RS-449 programmable rate interface, it is difficult to implement ATM based technology in a wireless environment using conventional interfaces because most ATM traffic is transmitted over high rate data interfaces.
Another difficulty associated with implementing ATM based technology in a wireless communication network has to do with the fact that ATM based protocols rely on extremely low bit error ratios which are typical of fiber optics based networks. By way of example, ATM protocols assume that the transmission medium has very low Bit Error Ratios (BER) (10xe2x88x9212) and that bit errors occur randomly.
In contrast, the bit error ratios associated with wireless communication are much higher (on the order of 10xe2x88x923 to 10xe2x88x928) and tend to fluctuate in accordance with atmospheric conditions. In addition, the errors associated with wireless communication tend to occur in longer bursts. Thus, a robust error correction scheme must be employed in a wireless network in which ATM-based technology is to be implemented.
A further constraint is that the cost of bandwidth in a wireless network is much higher than for fiber optics networks. As a consequence of having been traditionally implemented in fiber optics networks, ATM based technology is not particularly efficient in its use of transmission bandwidth. Therefore, if ATM-based technology is to be implemented in wireless networks, it must achieve a more efficient use of bandwidth.
In addition to the difficulties discussed above, there is another significant constraint placed on wireless communication networks. This constraint has to do with the transmission of ATM cells using a time divided transmission technique, such as TDMA and TDM, so that a limited system resource (bandwidth) can be shared by a large number of users. For example, during the establishment of a VCC in an ATM network, a traffic contract is negotiated between the source and the network. This traffic contract specifies the expected behavior of the source and the network. The behavior of the source is specified in terms of a traffic descriptor that describes the traffic that will be generated by the source. The traffic descriptor describes the traffic in terms of the Peak Cell Rate (PCR), Sustained Cell Rate (SCR), Maximum Burst Size (MBS) etc., which ever is applicable, as defined in the Traffic Management 4.0, ATM Forum Specification. The behavior of the network is specified in terms of the Quality of Service (QOS) that it will guarantee to the traffic belonging to the VCC. The QOS is specified in terms of the Cell Transfer Delay (CTD), Cell Delay Variation (CDV), Cell Loss Ratio (CLR), Cell Error Ratio (CER), Cell Misinsertion Rate (CMR) and Severely Errored Cell Block Ratio (SECBR). Of these, the former 3 are negotiated during the establishment of the traffic contract and the latter three take default values as defined in the ITU-TSS Recommendation I.356 BISDN ATM Layer Cell Transfer Performance.
The 2-point CDV is an important performance parameter for any ATM network. FIGS. 2A and 2B show how the 2-pt CDV is defined. With reference to FIG. 2A, the delay that cells going from node A and node B experience are plotted and the difference between the delay that more than xcex1 percent of the cells undergo and the minimum cell transfer delay is referred to as the xe2x80x9cpeak-to-peak 2-point CDVxe2x80x9d, as seen in FIG. 2B. The ITU-TSS Recommendation I.356 BISDN ATM Layer Cell Transfer Performance specifies that Class 1 or Constant Bit Rate (CBR) VCCs should experience a 2-point CDV of no more than 3 ms. Applications such as Circuit Emulation, Voice and Video would require such stringent 2-pt CDV performance from the network. User applications and devices are designed with this specification as the basis. So it is imperative that the ATM network guarantee the 3 ms CDV to be able to carry Class 1 or CBR traffic efficiently.
By way of example, without loss of generality, consider an ATM switch with 16 DS3 ports and analyze the CDV problem using 4 scenarios. ATM switches typically do most of the cell switching and other cell related functions in hardware and there would be negligible variation in the processing times. The CDV would be introduced because of differences in link speeds and framing structure in the ingress and egress links, queuing and scheduling.
Scenario 1: If there is only one VCC going from port 1 to port 2 in the ATM switch and there are no other VCCs, the CDV that cells will experience in the switch is 1 cell slot time of the egress link. A cell might arrive on the ingress link, just after a cell slot has begun on the egress link and hence the cell will have to wait a whole cell slot time of the egress link and then be transferred on the following cell slot. Since the egress link is a DS3 link, a cell slot time is about 9.4 microseconds (us).
Scenario 2: Consider 2 VCCs in the switch : one going from port 1 to port 3 and another going from port 2 to port 3. Consider the case, when cells from the VCCs on port 1 and port 2 arrive simultaneously, just after a cell slot has started on port 3. Consider also that the cell from the VCC on port 1 is scheduled to be transmitted before the cell from the VCC on port 2. In this case, the CDV experience by the cell from the VCC on port 2 is 2 cell slot times on the egress link. Since the egress link is a DS3 link, the CDV experienced by the cell is 18.8 (us).
Scenario 3: Consider 15 VCCs in the switch: VCC 1 goes from port 1 to port 16, VCC 2 from port 2 to port 16 and so on, and finally, VCC 15 goes from port 15 to port 16. Consider the event where cells from the VCCs on ports 1 through 15 arrive simultaneously to be transmitted on port 16. Assume, also that the cell from port 1 is transmitted first, the cell from port 2 is transmitted next and finally the cell from port 15 is transmitted on the link. In this case, the CDV experienced by the cell from the VCC on port 15 is 15 cell slot times on the egress link. On a DS3 egress link, this would be about 142 us.
Scenario 4: Consider a VCC being transmitted through 20 ATM switches all of which are 16 port ATM switches. Assume also, for simplicity, that all links in the network are DS3 links. Considering the worst case in each ATM switch, a cell would experience a cumulative CDV of 9.4 * 15 * 20 us which is 2.8 milliseconds (ms). This is within the 2-pt CDV values specified in ITU-TSS Recommendation I.356 BISDN ATM Layer Cell Transfer Performance.
It must be noted that on terrestrial networks, the full port bandwidth is at the disposal of the ATM switch, in contrast to the more limited amount of bandwidth that is available when the bandwidth resource is being shared by multiple terminals in a satellite or wireless network. The only reasons for any CDV in an ATM switch would be queuing, scheduling, differences in link speeds and framing structures and to a much lesser extent, processing delay. There is a further basis for CDV when ATM transmissions occur in a satellite or wireless system using TDMA.
Consider the flow of ATM cells and the framing structure in a TDMA network as shown in FIG. 3A-3C. In FIG. 3B, Terminal 1 has a terrestrial DS3 interface on which is transmits and receives ATM cells. It communicates via satellite 3 with Terminal 2 over a TDMA network. With reference to FIG. 3A, the TDMA frame period is typically designed to be between 16 to 48 ms, for efficiency purposes. The frames contain bursts that could either be signaling, control or traffic bursts. Traffic bursts are allocated for communication from one terminal to another. Information about this allocation is known to both the transmitting and receiving terminals. During the frame, the transmitting terminal waits for its burst and then transmits the information it has for the destination terminal. The destination terminal receives the burst and then transmits the received information on the terrestrial link.
Apart from the factors that affect 2-pt CDV in terrestrial networks, there are 2 other framing related factors that affect the CDV performance of a TDMA based ATM network. First, there are pre-allocated bursts in the TDMA frame for communication from one terminal to another. This introduces a 2-pt CDV of up to one TDMA frame period, which can be from 16-48 ms, as mentioned above. Second, traffic bursts in the TDMA frame could have bandwidth For several ATM cells. As an example, let us consider a traffic burst for 256 ATM cells. These 256 cells might arrive at the transmitting TDMA terminal from the terrestrial network in a well-spaced manner. These cells will be queued for transmission on the next available traffic burst. The cells arrive at the receiving TDMA terminal, which would then transmit these cells to the terrestrial network. Without any timing information, these cells would be transmitted back to back thus seriously deteriorating the 2-pt CDV performance of the TDMA network as shown in FIG. 3C.
The same factors as described above would affect a TDM-based network that also transmitted ATM cells. Pre-assigned slots for transmission to a particular terminal will introduce 2-pt CDV of up to a TDM frame period. Also, cells arrive at the receiving TDM terminal in a clumped manner, deteriorating the CDV performance of the TDM network further.
There are no known solutions which address the minimization of 2-point Cell Delay Variation of packet-type transmissions, such as ATM cells, frame relay packets or the like, over satellite and wireless networks. Moreover, the extension of this problem to other primary access interface systems would be clear to one of ordinary skill in the art.
For example, other primary access interfaces that would experience the foregoing problems include ISDN/SS#7 (for switched digital circuits, voice, fax and video conferencing) and packet-based system such as Internet and xe2x80x9cframe relayxe2x80x9d (for LAN interconnection and Internet access) using TCP/IP or other LAN protocols. Considerations similar to those for ATM are relevant to the transmission of traffic using these other interfaces, as exemplified by the transmission of frame/relay traffic over satellite/wireless networks, although some differences are known in the art.
For example, unlike ATM cells, frame relay packets are variable lengths. Thus, the frame formats used to communicate between the satellite/wireless terminals are arranged to transport variable length packets efficiently.
As explained in the Provisional Application Ser. No. 60-052,359, which is incorporated herein by reference, the frame/relay uses a robust, flexible frame format between two communicating terminals. This allows the transport of several variable sized Spackets (segmented packets) in a frame and also allows a single Spacket to be carried over several frames, whichever the case might be. Also, the frame format allows fast synchronization and the exchange of coding information. Each frame contains Reed-Solomon (RS) check bytes that are used for error correction and to enhance the quality of the satellite/wireless link. The number of RS check bytes in a frame can be changed on the fly, without any loss of data, to compensate for varying link conditions. The decision to change the RS check bytes in a frame is based on the constant monitoring of the link quality. Several frames are also interleaved before transmission over the satellite/wireless link, to help spread the effect of burst errors over several frames, all of which can then be corrected by the FEC in the frames.
Also, Virtual Channels (VCs) can be configured to be enabled for data compression, which means that the Spackets belonging to the VC are passed through a data compressor/decompressor combination to save bandwidth. VCs can also be configured to be either high or low priority VCs and the scheduler then, uses this information to fairly transmit the various Spackets over the satellite/wireless link. To minimize the large delays introduced by the transmission of low priority packets on a low bit rate link, and the delay experienced by high priority packets which are waiting to be scheduled, the Spacket allows the segmentation of large packets into several, smaller Spackets. The delays experienced by high priority packets are substantially reduced. This also allows for efficient implementation of the compression and decompression modules.
The frame relay arrangement using Spackets also faces the problem of efficiently using bandwidth in a wireless network. Therefore, if frame relay (Spacket)-based technology is to be implemented in wireless networks, it must achieve a more efficient use of bandwidth. These same goals apply to ISDN and SS#7 (ISDN/SS#7) transmissions, Internet transmissions and those generally using TCP/IP protocols. However, no solution to problems blocking achievement of these goals is seen in the prior art.
Accordingly, it is an object of the present invention to address and solve these problems.
The present invention overcomes the above-mentioned problems associated with implementing packet-type or cell-type transmissions in a wireless communication network that transmits via TDMA or TDM by providing a frame format for a communication signal containing a bit stream including packet formatted data.
The present invention overcomes the above-mentioned problems, particularly for ATM-type or frame relay-type transmissions, in a wireless communication network that transmits via TDMA or TDM by providing a frame format for a communication signal containing a bit stream including asynchronous transfer mode (ATM), ISDN/SS#7, Internet or frame relay-formatted data.
The invention concerns a portion of the time division (TDMA or TDM) system interface, which is located between an ATM switch and the WAN transmission device. The time division interface design is based upon an architecture and frame structure that encompasses TDM or TDMA frame assemble/disassemble functions.
Further, the present invention provides a time division frame structure and content that appends time and frame stamp information to each packet or cell, such that the original timing and position of each packet or cell relative to other packets and cells can be uniquely identified.
The present invention also provides an algorithm for appending a time and frame stamp to desired packet or cell transmissions that is simple and streamlined and can be implemented efficiently in software and simple hardware.
As used herein, the term xe2x80x9ccellxe2x80x9d shall be used to mean a fixed size container, such as the ATM cell, and the term xe2x80x9cpacketxe2x80x9d shall be used to mean and a variable size container, and the term xe2x80x9ccell/packetxe2x80x9d shall mean generically either or both such container arrangements.